/*
 * @Author: szx
 * @Date: 2021-11-08 13:49:40
 * @LastEditTime: 2021-11-08 14:10:52
 * @Description:
 * @FilePath: \leetcode\1-99\34\34.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
// class Solution {
//    public:
//     vector<int> searchRange(vector<int>& nums, int target) {
//         int start = -1, end = -1;
//         for (int i = 0; i < nums.size(); i++) {
//             if (nums[i] == target) {
//                 if (start == -1) {
//                     start = i;
//                 }
//                 end = i;
//             }
//         }
//         return {start, end};
//     }
// };

class Solution {
   public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = -1, end = -1;
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (r == 0) {
            return {-1, -1};
        }
        for (int i = l - 1; i >= 0; i--) {
            if (nums[i] == target) {
                if (end == -1) {
                    end = i;
                }
                start = i;
            } else {
                break;
            }
        }
        return {start, end};
    }
};

int main() {
    Solution s;
    vector<int> v{1};
    vector<int> res = s.searchRange(v, 1);
    cout << res[0] << " " << res[1];
    return 0;
}